剑指offer62题；二叉搜索树的第K个节点
//二叉搜索树的题首先应该联想到二叉搜索树的性质，中序遍历是一组升序序列
//所以解题思路可以使用中序遍历来做
import java.util.Stack;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution{
	TreeNode KthNode(TreeNode pRoot,int k){
		if(pRoot==null||k<=0)return pRoot;//特殊用例，pRoot为空或者k非法
		Stack<TreeNode> stack=new Stack<>();
		TreeNode cur=pRoot;
		while(!stack.isEmpty()||cur!=null){//中序遍历
			if(cur!=null){
				stack.push(cur);
				cur=cur.left;
		}else{
				cur=stack.pop();
				if(--k==0){//一定是--k，先减因为数组下标的特性，输出第五小，返回下标为4
				return cur;
				}
				cur=cur.right;
			}
		}
	}
}